Міністерство освіти і науки України Національний університет «Львівська політехніка»
В.О.Костовський «ТЕОРІЯ АЛГОРИТМІВ ТА МАТЕМАТИЧНІ ОСНОВИ ПРЕДСТАВЛЕННЯ ЗНАНЬ» М е т о д и ч н i в к а з i в к и д о к у р с у л е к ц і й для студентів бакалаврату базового напрямку “Комп‘ютнрні науки” Кафедра “Автоматизовані системи управління” Курс ІV Львів -2002 Конспект лекцій по ТА МОПЗ - 2002/2003 Методичні вказівки склав Доцент кафедри АСУ В.О.Костовський      (вчене звання, посада викладача)      (підпис)  (прізвище, ініціали)  "___"____________2002 р.   Методичні вказівки розглянуті та схвалені на засіданні кафедри «Автоматизовані системи управління»  (найменування кафедри, за якою закріплена дисципліна)  Протокол №___ від "___"________________2002 р.   Завідувач кафедри   Рашкевич Ю.М.   (підпис)  (прізвище, ініціали)   ВСТУП Ці методичні вказівки до курсу лекцій з курсу «Теорія алгоритмів та математичні основи представлення знань» (ТА МОПЗ) розроблені з метою полегшення вивчення студентами основних тем даного курса відповідно до програми з ТА МОПЗ. При викладі сутевим чином використовуються підходи робіт [1,2,3]. Тема "Алгоритмічні проблеми" §1 Алгоритми обчислювальні процедури Навчаючи арифметиці в початковій школі, ми познайомилися з додаванням і множенням двох чисел. Нам у явній формі не говорили, що в будь-якої пари чисел існують добуток і сума, а вказали способи і правила їхнього знаходження. Такі способи і правила є прикладами алгоритмів, і обчислювальних (ефективних) процедур. Їхнє застосування не вимагає чи винахідливості чи кмітливості, учню необхідно було тільки слідувати інструкціям учителя. Більш загально, алгоритм, чи ефективна процедура,-це механічне правило чи автоматичний метод, чи програма для виконання деяких математичних операцій. Приведемо ще кілька прикладів операцій, для яких легко можна вказати алгоритми: (1.1) (а) по даному п знайти n-e просте число; (b) диференціювання полінома; (c) знаходження найбільшого загального дільника двох натуральних чисел (алгоритм Евклида); (d) для двох даних чисел х, у вирішити, чи є х кратним у. Неформально і схематично алгоритм представлений на мал. 1а. На вхід подається інформація чи об'єкт, що підлягає обробці (наприклад, поліном у прикладі (1.1) (b), пари натуральних чисел у прикладах (1.1) (с) і (d)), а виходом є результат обробки операції над входом (так, для (1.1) (b) це похідна полінома, а для (1.1) (d)—відповідь «так» чи «ні»). Вихід виробляється автоматично чорним ящиком-який може бути комп'ютером або школярем, що діє по інструкції, чи навіть дуже розумним добре тренованим собакою. Алгоритм є процедура (чи спосіб обчислення), здійснювана чорним ящиком для одержання виходу з входу. Якщо алгоритм, чи ефективна процедура, використовується для обчислення значень числової функції, то ця функція називається ефективно вычислимой, чи алгоритмічно вычислимой, чи просто вычислимой. Наприклад, функції ху, Вхід вихід НОД(х,у)= найбільший загальний дільник чисел х и у и f(n)= просте число вираховувані в неформальному змісті, як уже відзначалося вище. Розглянемо, з іншого боку, наступну функцію: 1, якщо в десятковому розкладанні числа pi знайдеться g(n)== рівно п підряд йдущих цифр 7; 0 у противному випадку. Більшість математиків вважають, що g є цілком «законною» функцією. Але чи вираховувана функція g? Існує механічна процедура для послідовного породження цифр у десятковому розкладанні pi, тому напрошується «процедура» для обчислення функції g. «При заданому п почніть обчислювати десятковий розклад pi по одній цифрі за один такт часу і відзначайте появу сімок. Якщо на якому-небудь кроці з'явиться відрізок, що складається рівно з п сімок, зупините процес обчислення і покладете g(n}=0. Якщо такий відрізок не буде обнаружен, то покладете g(n)=0». Недоліком цієї «...